using System.Collections.Generic;

public class LimitedCache<T>
{
    private readonly int capacity;
    private readonly Dictionary<string, T> cache = new();
    private readonly LinkedList<string> lruList = new();

    public LimitedCache(int capacity)
    {
        this.capacity = capacity;
    }

    public T Get(string key, System.Func<string, T> valueFactory)
    {
        if (cache.TryGetValue(key, out var value))
        {
            lruList.Remove(key);
            lruList.AddFirst(key);
            return value;
        }

        value = valueFactory(key);
        Put(key, value);
        return value;
    }

    public void Put(string key, T value)
    {
        if (cache.ContainsKey(key))
        {
            lruList.Remove(key);
        }
        else if (cache.Count >= capacity)
        {
            string oldestKey = lruList.Last.Value;
            lruList.RemoveLast();
            cache.Remove(oldestKey);
        }

        cache[key] = value;
        lruList.AddFirst(key);
    }

    public bool TryGet(string key, out T value)
    {
        if (cache.TryGetValue(key, out value))
        {
            lruList.Remove(key);
            lruList.AddFirst(key);
            return true;
        }
        return false;
    }

    public void Clear()
    {
        cache.Clear();
        lruList.Clear();
    }
}
